#ifndef __tree_lkjjwfejiojoiwef93323290i98u9hy7yf43jifejji2efjnvnjv__
#define __tree_lkjjwfejiojoiwef93323290i98u9hy7yf43jifejji2efjnvnjv__

#include <list>
#include <algorithm>
#include <type_traits>

#include "../base/base_type.hpp"
#include "../base/optional.hpp"

namespace muses {
	namespace utils
	{
		namespace tree
		{
			/**********************************************************************************************
			 * @brief iterator_t
			 */
			template< typename _node, typename _iterator >
			struct iterator_t
			{
				typedef _node node_t;
				typedef _iterator base_iterator;

				typedef iterator_t< node_t, base_iterator > this_t;

				typedef std::list< std::pair< base_iterator, base_iterator > > path_t;

				path_t path_;

				iterator_t() {}

				iterator_t( base_iterator b, base_iterator e )
				{
					path_.push_back( std::make_pair( b, e ) );
				}

				iterator_t( const iterator_t& itr ) :
					path_( itr.path_.begin(), itr.path_.end() )
				{
				}

				const path_t& path() const { return path_; }

				node_t& operator*() { return *( path_.back().first ); }
				node_t* operator->() { return &*( path_.back().first ); }

				void return_iterator()
				{
					if ( path_.back().first == path_.back().second )
					{
						path_.pop_back();

						if ( !path_.empty() )
						{
							++( path_.back().first );

							return_iterator();
						}
					}
				}

				bool add_itrator()
				{
					if ( !path_.empty() )
					{
						auto& itr = path_.back().first;

						if ( itr->nodes_ )
						{
							path_.push_back( std::make_pair( itr->nodes_->begin(), itr->nodes_->end() ) );
						} else {
							++itr;
						}

						return_iterator();
					}

					return !path_.empty();
				}

				iterator_t& operator=( const iterator_t& itr )
				{
					if ( this != &itr )
					{
						std::copy( itr.path_.begin(), itr.path_.end() );
					}

					return *this;
				}

				this_t& operator++( int )
				{
					this_t ret( *this );

					add_itrator();

					return ret;
				}

				this_t operator++()
				{
					add_itrator();

					return *this;
				}
			};

			template< typename _n, typename _i >
			inline bool operator==( iterator_t< _n, _i > a, iterator_t< _n, _i > b )
			{
				if ( a.path_.size() == b.path_.size() )
				{
					auto ia = a.path_.cbegin();
					auto ib = b.path_.cbegin();

					for ( size_t i = 0; i < a.path_.size(); ++i )
					{
						if ( *ia != *ib ) return false;

						++ia;
						++ib;
					}

					return true;
				} else {
					return false;
				}
			}

			template< typename _n, typename _i >
			inline bool operator!=( iterator_t< _n, _i > a, iterator_t< _n, _i > b )
			{
				return !operator==( a, b );
			}

			/**********************************************************************************************
			 * @brief node_t
			 */
			template< typename _value >
			struct node_t
			{
				typedef _value value_t;
				typedef node_t< _value > this_t;

				typedef typename std::add_lvalue_reference< value_t >::type       refrence_t;
				typedef typename std::add_lvalue_reference< const value_t >::type const_refrence_t;

				typedef std::list< this_t > list_t;

				typedef typename list_t::iterator base_iterator;
				typedef typename list_t::const_iterator base_const_iterator;

				typedef typename tree::iterator_t< node_t,       typename node_t::base_iterator >       iterator;
				typedef typename tree::iterator_t< const node_t, typename node_t::base_const_iterator > const_iterator;

				hude::optional_t< list_t > nodes_;
				hude::optional_t< value_t > value_;
				
				node_t( const_refrence_t v, list_t&& nodes ) : value_( v ), nodes_( hude::optional_t< list_t >( list_t( nodes ) ) ) {}
				node_t( const_refrence_t v ) : value_( v ) {}

				node_t() {}

				size_t size() const
				{
					size_t ret = 0;

					if ( nodes_ )
					{
						std::for_each( nodes_->begin(), nodes_->end(), [this, &ret]( const this_t& node ) -> void
						{
							ret += node.size();
						} );
					}

					return ret + 1;
				}

				size_t deep() const
				{
					size_t ret = 0;

					if ( nodes_ )
					{
						std::for_each( nodes_->begin(), nodes_->end(), [this, &ret]( const this_t& node ) -> void
						{
							auto tmp = node.deep();
							ret = ( tmp > ret ) ? tmp : ret;
						} );
					}

					return ret + 1;
				}

				void value( const_refrence_t v )
				{
					value_ = hude::optional_t< value_t >( v );
				}

				hude::optional_t< value_t > value() { return value_; }
				const hude::optional_t< value_t > value() const { return value_; }

				iterator begin() { return ( !nodes_ ) ? iterator() : iterator( nodes_->begin(), nodes_->end() ); }
				iterator end() { return iterator(); }

				const iterator begin()  const { return ( !nodes_ ) ? const_iterator() : const_iterator( nodes_->cbegin(), nodes_->cend() ); }
				const iterator end()    const { return const_iterator(); }
			};
		} //namespace tree

		template< typename _value >
		class tree_t
		{
		public:
			typedef _value value_t;
			typedef tree_t< value_t > this_t;

			typedef typename utils::tree::node_t< _value > node_t;
			typedef typename node_t::list_t children_t;

			typedef typename node_t::iterator iterator;
			typedef typename node_t::const_iterator const_iterator;

		public:
			size_t size() const { return root_.size() - 1; }
			size_t deep() const { return root_.deep() - 1; }

			bool empty() const { return ( root_.nodes_ && !root_.nodes_->empty() ); }

			void clear() { root_ = hude::optional_null_t(); }

			void root( typename node_t::const_refrence_t v )
			{
				typename node_t::list_t r{ node_t( v ) };
				root_.nodes_ = hude::optional_t< typename node_t::list_t >( r );
			}

			node_t& root() { return root_.nodes_->front(); }
			const node_t& root() const { return root_.nodes_->front(); }

			iterator begin() { return root_.begin(); }
			iterator end()   { return root_.end(); }

			const_iterator begin() const { return root_.begin(); }
			const_iterator end()   const { return root_.end(); }

		private:
			node_t root_;

		};

		/**********************************************************************************************
		 * @brief level_t
		 */
		template< typename _value >
		struct level_t
		{
			typedef _value value_t;
			typedef int8_t index_t;
			typedef level_t< value_t > this_t;
			typedef uint8_t sec_t;

			value_t& value_;
			index_t index_;

			level_t( value_t &value, index_t index ) : value_( value ), index_( index * 4 ) {}

			void cls() { value_ &= ~( 0x0f << index_ ); }
			sec_t get() const { return ( value_ >> index_ ) & 0x0f; }
			void set( sec_t v ) { cls(); value_ |= ( ( v & 0x0f ) << index_ ); }

			this_t& operator=( sec_t v ) { set( v ); return *this; }
			operator sec_t() const { return get(); }

			//this_t operator+( sec_t v ) { this_t ret( value_t, this->index_ ); ret.set( get() + v ); return ret; }
			//this_t operator-( sec_t v ) { this_t ret( value_t, this->index_ ); ret.set( get() - v ); return ret; }

			this_t operator+=( sec_t v ) { set( get() + v ); return *this; }
			this_t operator-=( sec_t v ) { set( get() - v ); return *this; }
		};

		/**********************************************************************************************
		 * @brief index_t
		 */
		template< typename _value >
		struct index_t
		{
			typedef _value value_t;
			typedef index_t< value_t > this_t;

			typedef level_t< value_t >       normal_level_t;
			typedef level_t< const value_t > const_level_t;

			typedef typename normal_level_t::index_t idx_t;

			enum { emSIZE = sizeof( value_t ) * 2 };

			value_t index_;
			
			index_t( value_t a ) : index_( a ) {}
			index_t() : index_t( 0 ) {}

			value_t value() const { return index_; }

			idx_t pos(idx_t idx) { auto cut = idx_t( count() );  return ( idx < 0 )? cut + idx : idx; }

			normal_level_t at( idx_t idx )       { return normal_level_t( index_, pos( idx ) ); }
			const_level_t  at( idx_t idx ) const { return const_level_t ( index_, pos( idx ) ); }

			normal_level_t count()       { return normal_level_t( index_, emSIZE - 1 ); }
			const_level_t  count() const { return const_level_t ( index_, emSIZE - 1 ); }

			normal_level_t last()       { return at( -1 ); }
			const_level_t  last() const { return at( -1 ); }

			normal_level_t operator[]( idx_t idx )       { return at( idx ); }
			const_level_t  operator[]( idx_t idx ) const { return at( idx ); }

			index_t operator+( typename normal_level_t::sec_t v )
			{
				index_t ret = *this;

				auto c = ret.count();
				c.set( c.get() + 1 );

				auto r = ret[c.get() - 1];
				r.set( r.get() + v );

				return ret;
			}
		};

		template< typename _value >
		inline bool operator< ( index_t< _value > a, index_t< _value > b ) { return a.index_ < b.index_; }

		template< typename _value >
		inline bool operator==( index_t< _value > a, index_t< _value > b ) { return a.index_ == b.index_; }

		template< typename _value >
		inline bool operator!=( index_t< _value > a, index_t< _value > b ) { return a.index_ != b.index_; }

	} //namespace utils
} //namespace muses

#endif //__tree_lkjjwfejiojoiwef93323290i98u9hy7yf43jifejji2efjnvnjv__

